package Demo01;
public class Test {
    public static void main(String[] args) {
        Solution solution = new Solution();
        ListNode node = new ListNode(2);
        ListNode node1 = new ListNode(4);
        node.next = node1;
        ListNode node2 = new ListNode(3);
        node1.next = node2;

        ListNode node3 = new ListNode(5);
        ListNode node4 = new ListNode(6);
        node3.next = node4;
        ListNode node5 = new ListNode(4);
        node4.next = node5;
        ListNode curNode = solution.addTwoNumbers(node,node3);
        while (curNode!=null) {
            System.out.println(curNode.val);
            curNode = curNode.next;
        }
    }
}
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null||list2==null) {
            return list1==null?list2:list1;
        }
        ListNode head = (list1.val>=list2.val)?list2:list1;
        ListNode lastHeadListNode = head;
        ListNode curNode1 = head.next;
        ListNode curNode2 = (list1==head)?list2:list1;
        while(curNode1!=null&&curNode2!=null) {
            if(curNode1.val>curNode2.val) {
                head.next = curNode2;
                curNode2 = curNode2.next;
            }else {
                head.next = curNode1;
                curNode1 = curNode1.next;
            }
            head = head.next;
        }
        if(curNode1!=null) {
            head.next = curNode1;
        }
        if(curNode2!=null) {
            head.next = curNode2;
        }
        return lastHeadListNode;
    }
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int tmp = 0;
        ListNode head = l1;
        ListNode cur = null;
        while(l1!=null&&l2!=null) {
            int sum = l1.val+l2.val+tmp;
            l1.val = sum%10;
            tmp = sum/10;
            cur = l1;
            l1 = l1.next;
            l2 = l2.next;
        }
        if(l2!=null) {
            cur.next = l2;
        }
        while(l2!=null) {
            int sum = tmp+l2.val;
            tmp = sum/10;
            l2.val = sum%10;
            cur = l2;
            l2 = l2.next;
        }
        if(tmp!=0) {
            ListNode newNode = new ListNode(tmp);
            cur.next = newNode;
        }
        return head;
    }
    public ListNode partition(ListNode head, int x) {
        if (head == null||head.next==null) {
            return head;
        }
        ListNode f = null;
        ListNode s = null;
        ListNode cur = head;
        ListNode tmp = null;
        ListNode tmp2 = null;

        while (cur != null) {
            if (cur.val >= x) {
                if (f == null) {
                    f = cur;
                    tmp = f;
                } else {
                    f.next = cur;
                    f = f.next;
                }
            } else {
                if (s == null) {
                    s = cur;
                    tmp2 = s;
                } else {
                    s.next = cur;
                    s = s.next;
                }
            }
            cur = cur.next;
        }
        if (f != null) {
            f.next = null;
        }
        if (s != null) {
            s.next = tmp;
        }
        if(tmp2!=null) {
            return tmp2;
        }
        return tmp;
    }
}